package point;

/**题目：把数组中0移动到数组末端，并且要保证数据中元素的相对位置不变
 * y:[1,0,2,0,6]    ---> [1,2,6,0,0]
 * @Author Gavin
 * @date 2022.01.10 21:59
 */
public class solution_1 {
    /**
     * 第一种方法：
     * 使用一个快慢指针slow,fast
     * 如果fast指向一个非零的下标，那么就把这个元素移动到slow的下标位置，
     * 然后slow和fast都向后移动一位。
     * 如果fast指向的是一个0，那么slow保持不变，然后fast向后移动一位，最后
     * fast移动到末尾之后就把slow后面的下标都置为0就行
     */
    //Time:O(n) Space:O(1)
    public void solution_1(int[] nums){
        if(nums==null||nums.length==0)return;
        int slow=0;
        for (int fast = 0; fast <nums.length ; fast++) {
            if(nums[fast]!=0){
                nums[slow]=nums[fast];
                ++slow;
            }
        }
        for (int i = slow; i <nums.length ; i++) {
            nums[i]=0;
        }
    }

    /**
     * 第二种方法：相比与第一种方法的优化点就在于最后一个循环把
     * slow后面的数都置为零，这里的优化点就是通过交换快慢下标的置来
     * 达到置零
     */
    //Time:O(n) Space:O(1)
    public void solution_2(int[] nums){
        if(nums==null||nums.length==0)return;
        int slow=0;
        for (int fast = 0; fast <nums.length ; fast++) {
            if(nums[fast]!=0){
                int tmp=nums[slow];
                nums[slow]=nums[fast];
                nums[fast]=tmp;
                ++slow;
            }
        }
    }
}
